\documentclass[11pt]{ctexart}
\usepackage{graphicx}
\usepackage{ctex}
\usepackage[a4paper,left=1.25in,right=1.25in,top=1in,bottom=1in]{geometry}

\graphicspath{ {../images/} }
\raggedbottom	% 令页面在垂直方向向顶部对齐
\everymath{\displaystyle}   % 行内公式采用行间公式格式排列
\title{Sorting测试报告}
\author{刘小川 \qquad 3210105317}


\begin{document}
\maketitle
\CTEXsetup[format={\Large\bfseries}]{section}

\section{测试思路}
\begin{enumerate}
\item
在本作业的要求中，有关于测试数据分别为1\%,10\%,90\%,99\%有序的要求，为了达成这一要求，在
测试设计main函数时，先规定N为数组的长度，关于N\%的有序，我计划是令这个数组的前N\%长度
为从0开始的递增数组，如果N为10000,有序度为1\%，则100个元素为0到100;有序度为10\%，则前1000
个元素为0到1000。
\item
有了测试用的数组，我们需要对同一个测试的数组，分别用heapsort和quicksort来测试（注意在测试中，测试完第一个
直接用来测试第二个，因为测试后数组变成完全有序，会影响排序效率，我们可以用另一个向量深度复制前
一个向量，来保证两次测试都是有一定的有序度），不断改变N，分别
来记录下每个N所对应的排序效率，做完一系列测试后，在改变测试数组的有序度，再继续进行测试。
在我使用的main测试程序中，我设置了一个输入数据为N数组长度，在该程序中若想改变测试所用的有序度
则需要使用不同的vector，其中vector1,2,3,4分别对应有序度1\%,10\%,90\%,99\%。在使用其中一个vector时
我们将其他的vector先注释掉，防止占用过多的内存
下面我以有序度10\%为例
在10\%下，下方排序所用向量为vector2,
{
\centering\includegraphics[width=0.9\textwidth]{Graph1.png}

}\par
经过此图我发现在20000到10000之间quicksort算法更快一些

\end{enumerate}
\section{改进方法}
老师上课所讲的优化方法，在原代码中已经有所体现，分别是当数组小于一定长度insertion排序的使用以及取的基准为三数平均。那么除此之外，优化方法还有尾递归优化即将所有的递归形式，如果一个函数所有的递归形式调用出现在函数末尾，当递归
调用是整个函数体中最后执行的语句且他的返回值不属于表达式部分，这个递归就是尾递归。当编译器检测到尾递归时，它覆盖当前活动记录而不是在栈中创建一个新的。编译器做到这点，通过覆盖当前栈帧而不是在其之上重新添加一个，这样所使用栈空间大大缩减，实际运行效率提高。比如f(n, sum) = f(n-1) + value(n) + sum; 会保存n个函数调用堆栈，而使用尾递归f(n, sum) = f(n-1, sum+value(n)); 这样则只保留后一个函数堆栈即可，之前的可优化删去。下面是尾递归的简单例证\par
这是两种递归的简单对比，通过简单的5的阶乘体现。

{
\centering\includegraphics[width=0.8\textwidth]{picture1.png}\par

}\par
{
\centering\includegraphics[width=0.8\textwidth]{picture1.png}\par

}\par
若将其应用到快速排序中，思路就是在递归是，左参数使用一次后没有作用，就可以用递归控制结构代替。这种优化原理是对递归优化来减少栈深度。


\end{document}